#!/usr/bin/env python
from __future__ import division

from euclid import Point3, Line3, Ray3, Plane as EuclidPlane, Sphere as EuclidSphere
from collections import namedtuple
from itertools import combinations

class Triangle(namedtuple("Triangle", "a b c")):
    def plane(self):
        v1 = self.b - self.a
        v2 = self.c - self.a
        normal = v1.cross(v2)
        return Plane(self.a, normal)

    def contains(self, point):
        #print point
        plane = self.plane()
        if plane.distance(point) > 0.4:
            return False
        # Based on: http://mathworld.wolfram.com/TriangleInterior.html
        v0 = self.a
        v1 = self.b - self.a
        v2 = self.c - self.a
        v = point
        n = plane.n

        a = n.dot(v.cross(v2) - v0.cross(v2))/n.dot(v1.cross(v2))
        b = -n.dot(v.cross(v1) - v0.cross(v1))/n.dot(v1.cross(v2))

        return a>=0 and b>=0 and a+b<=1

    def intersect(self, line):
        plane = self.plane()
        inter = plane.intersect(line)
        #print "inter = {0}".format(inter)
        if inter and self.contains(inter[0][0]):
            return inter
        return []

    def __eq__(self, other):
        return cmp(self, other) == 0

    def __cmp__(self, other):
        points = list(self)
        other_points = list(other)
        points.sort()
        other_points.sort()
        return cmp(points, other_points)


class Pyramid(namedtuple("Pyramid", "a b c d")):
    def faces(self):
        l = []
        for i in range(4):
            points = list(self)
            outer = points.pop(i)
            v1 = points[1] - points[0]
            v2 = points[2] - points[0]
            v  = outer - points[0]
            if v.dot(v1.cross(v2)) < 0:
                l.append(Triangle(*points))
            else:
                l.append(Triangle(points[0], points[2], points[1]))
        return l

    def intersect(self, ray):
        possible_points = []
        for face in self.faces():
            intersect = face.intersect(ray)
            possible_points += intersect
        return possible_points

class Plane(EuclidPlane):
    def intersect(self, other):
        point = EuclidPlane.intersect(self, other)
        if point is not None:
            return [(point, self.n)]
        return []

class Sphere(EuclidSphere):
    def intersect(self, other):
        segment = EuclidSphere.intersect(self, other)
        if segment is None:
            return []

        p1, p2 = segment.p1, segment.p2
        return [(p1, (p1 - self.c).normalize()), (p2, (p2 - self.c).normalize())]










